package heap.indexMaxHeap;

/**
 * 最大索引堆，由于交换比较复杂的元素会造成性能的下降，所以通过交换元素的索引，性能会大大提高
 * mxf
 * 2018-6-5 11:40:05
 */
public class IndexMaxHeap<Item extends Comparable> {
    protected Item[] data; // 数组
    protected int[] indexes; // 索引
    protected int count; // 元素的个数
    protected int capacity; // 数组的长度

    // 构造函数, 构造一个空堆, 可容纳capacity个元素
    public IndexMaxHeap(int capacity){
        this.data = (Item[])new Comparable[capacity+1];
        this.indexes = new int[capacity + 1];
        this.count = 0;
        this.capacity = capacity;
    }

    // 返回堆中的元素个数
    public int size(){
        return count;
    }

    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty(){
        return count == 0;
    }

    // 对于外部用户而言，索引是从0开始的
    public void insert(int i, Item item) {
        assert count + 1 <= capacity;
        assert i + 1 >= 1 && i + 1 <= capacity;
        i += 1;
        data[i] = item;
        indexes[count+1] = i;
        count ++;

        shiftUp(count);
    }

    //********************
    //* 最大堆核心辅助函数
    //********************
    private void shiftUp(int k) {
        while (k > 1 && data[indexes[k]].compareTo(data[indexes[k / 2]]) > 0) {
            swap(k, k / 2);
            k = k / 2;
        }
    }

    public Item extractMax() {
        assert count > 0;
        Item max = data[indexes[1]];
        swap(1, count);
        count--;
        shiftDown(1);
        return max;
    }

    // 获取最大值的索引
    public int extractMaxIndex() {
        assert count > 0;
        int max = indexes[1] - 1;
        swap(1, count);
        count--;
        shiftDown(1);
        return max;
    }

    // 获取最大索引堆中的堆顶元素
    public Item getMax(){
        assert count > 0;
        return data[indexes[1]];
    }

    // 获取最大索引堆中的堆顶元素的索引
    public int getMaxIndex(){
        assert count > 0;
        return indexes[1]-1;
    }

    // 获取最大索引堆中索引为i的元素
    public Item getItem( int i ){
        assert i + 1 >= 1 && i + 1 <= capacity;
        return data[i+1];
    }

    public void change(int i, Item newItem) {
        i += 1;
        data[i] = newItem;

        for(int j = 1; j <= count; j++) {
            if(indexes[j] == i) {
                shiftUp(j);
                shiftDown(j);

                return;
            }
        }
    }

    private void shiftDown(int k) {
        while(2 * k <= count) {
            int j = 2 * k;
            if(j + 1 <= count && data[indexes[j]].compareTo(data[indexes[j + 1]]) < 0) {
                j++;
            }
            if(data[indexes[k]].compareTo(data[indexes[j]]) > 0) {
                break;
            }
            swap(k, j);
            k = j;
        }
    }

    // 交换堆中索引为i和j的两个元素
    private void swap(int i, int j){
        int t = indexes[i];
        indexes[i] = indexes[j];
        indexes[j] = t;
    }



    // 测试 MaxHeap
    public static void main(String[] args) {

        heap.shiftDown.MaxHeap<Integer> maxHeap = new heap.shiftDown.MaxHeap<Integer>(100);
        int N = 100; // 堆中元素个数
        int M = 100; // 堆中元素取值范围[0, M)
        for( int i = 0 ; i < N ; i ++ )
            maxHeap.insert( new Integer((int)(Math.random() * M)) );

        Integer[] arr = new Integer[N];
        // 将maxheap中的数据逐渐使用extractMax取出来
        // 取出来的顺序应该是按照从大到小的顺序取出来的
        for( int i = 0 ; i < N ; i ++ ){
            arr[i] = maxHeap.extractMax();
            System.out.print(arr[i] + " ");
        }
        System.out.println();

        // 确保arr数组是从大到小排列的
        for( int i = 1 ; i < N ; i ++ )
            assert arr[i-1] >= arr[i];

    }
}
